﻿'''
题目描述
给定一个单链表 L，请编写程序输出 L 中间结点保存的数据。
如果有两个中间结点，则输出第二个中间结点保存的数据。
例如：
给定 L 为 1→7→5，则输出应该为 7；
给定 L 为 1→2→3→4，则输出应该为 3。
输入描述
每个输入包含 1 个测试用例。每个测试用例:
第 1 行给出链表首结点的地址、结点总个数正整数 N (≤105)。
结点的地址是 5 位非负整数，NULL 地址用 −1 表示。
接下来有 N 行，每行格式为：
Address Data Next 
其中 Address 是结点地址，Data 是该结点保存的整数数据(0 ≤ Data ≤ 108)，Next 是下一结点的地址。
输出描述
对每个测试用例，在一行中输出 L 中间结点保存的数据。
如果有两个中间结点，则输出第二个中间结点保存的数据。
( 如果奇数个节点取中间，偶数个取偏右边的那个值)
示例1
输入
00010 4
00000 3 -1
00010 5 12309
11451 6 00000
12309 7 11451
输出
6
示例2
输入
10000 3
76892 7 12309
12309 5 -1
10000 1 76892
输出
7
示例3
输入
00100 4
00000 4 -1
00100 1 12309
33218 3 00000
12309 2 33218
输出
3
解题思路
示例 1：
链表为：5 -> 7 -> 6 -> 3，长度为 4，偶数节点，因此中间两个节点是 7 和 6，输出第二个中间结点的值：6。
示例 2：
链表为：1 -> 7 -> 5，长度为 3，奇数节点，中间结点是 7，输出 7。
示例 3：
链表为：1 -> 2 -> 3 -> 4，长度为 4，偶数节点，中间两个节点是 2 和 3，输出第二个中间结点的值：3。
这道题的要求是给定一个单链表，输出它的中间结点的数据。如果链表长度是奇数，那么中间结点就是第{n+1}/{2}个结点（第一个结点
为第1个）；如果链表长度是偶数，则中间结点是第{n}/{2} + 1个结点，也就是偏右的那个结点。
通过输入中的 Address、Data、Next 信息，首先建立链表的结构。，使用快慢指针法，一个指针每次移动两步，另一个指针每次移动
一步，当快指针到达链表末尾时，慢指针刚好位于中间节点。对于偶数长度的链表，这样的算法能自动返回偏右的那个节点。
'''
#读取输入
head_addr,n = input().split()

#用字典存储节点信息
node_info = {}

for _ in range(int(n)):
    addr,data,next_addr = input().split()
    node_info[addr] = [data,next_addr]
#使用快慢指针，快指针每次走两步，慢指针每次走一步，这样快指针到达链表末尾时，慢指针刚好对应要求的中间节点
slow = head_addr
fast = head_addr

while fast != '-1' and fast in node_info:
    #快指针走一步
    fast = node_info[fast][1]
    if fast == '-1' or fast not in node_info:   #如果到达末尾,跳出循环
        break
    fast = node_info[fast][1]
    slow = node_info[slow][1]
#输出slow指向的数据
print(node_info[slow][0])
